
/*
 * Problem: 理想路径（Ideal Path）
 * Author: Yuanshun L
 * Created: 7-Nov-2021
 */

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>

using namespace std;

const int maxn =  1000+10;
const int maxm =  2000+10;
const int INF = 10e7;

int g[maxn][maxn];  // 邻接矩阵
int d[maxn]; // 某点到其他点的距离，这里的某点会是起点或者终点
int vis[maxn];
int n; // 结点数量
vector<int> path;

void recurse(int end){

    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(end);
    vis[end] = 1;
    d[end] = 0;

    // 层次遍历
    while(!q.empty()){
        int t = q.front(); q.pop();
        for(int i=1;i<=n;i++){
            // 为本身、被访问过、没有直接邻接
            if(i == t || vis[i] || !g[i][t]) continue;
            d[i] = d[t] + 1;
            vis[i] = 1;
            q.push(i);
        }
    }
}

void solve(int start){

    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(start);

    vector<int> vc;
    vc.push_back(start);

    while(!vc.empty()){
        int  min = INF;
        vector<int> vc2;
        vector<int> vc3;
        for(int i=0;i<vc.size();i++){
            int  t = vc[i];
            for(int j=1; j<=n; j++){
                // 为本身、被访问过、没有直接邻接，不沿着最短路径
                if(t == j || g[t][j] == 0 || d[j]+1!=d[t]) continue;

                vc2.push_back(j);
                vc3.push_back(g[t][j]);
                if(min > g[t][j]) min = g[t][j];
            }
        }

        if(vc2.size() == 0) break;

        vc.clear();
        for(int i=0;i<vc2.size();i++){
            int id = vc2[i];
            if(vc3[i] == min) vc.push_back(id);
        }
        path.push_back(min);
        vc2.clear();vc3.clear();
    }
}

void print_ideal_path(){
    int first = 0;
    cout<<path.size()<<endl;
    for(int i=0;i<path.size();i++){
        if(first++) cout <<" ";
        cout << path[i];
    }
    cout<<endl;
}

int main(){


    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);

    int m; // 边的数量
    int x1,x2,dist;
    memset(g,0,sizeof(g));
    cin >> n >> m;
    while(m--){
        cin >> x1 >> x2 >> dist;
        if(!g[x1][x2] || g[x1][x2] > dist){
            g[x1][x2] =  g[x2][x1] = dist;
        }

    }

    recurse(n);
    solve(1);
    print_ideal_path();


    return 0;
}